// 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
// 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
// 例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

function minArray(numbers: number[]): number {
  let left: number = 0; // 左指针
  let right: number = numbers.length - 1; // 右指针
  // 二分查找框架
  while (left < right) {
    let mid: number = Math.floor((left + right) / 2); // 求解得到中指针
    if (numbers[mid] > numbers[right]) {
      left = mid + 1; // 剔除掉包含mid指针在内的左半区间
    } else if (numbers[mid] < numbers[right]) {
      right = mid; // 剔除掉不含mid指针在内的右半区间
    } else if (numbers[mid] === numbers[right]) {
      right--; // 注意，此时无法准确判断数组情况，但可以肯定right指针不是最小元素
    }
  }
  return numbers[left];
}

// 这道题是一道比较基础的和二分查找相关的题目
// 这道题我们要查找的目标其实也比较的明确，就是排序数组的最小元素
// 我们设置两个左右指针分于数组的两端，按照常规的二分模板书写代码
// 当mid大于右指针时，mid一定存在于旋转数组中被挪动的数组部分
// 因此我们直接排除mid的左半边，让左指针为mid指针+1，丢弃包含mid的左半区间
// 当mid小于右指针时，mid一定存在于旋转数组中没有被挪动的部分
// 因此我们可以抛弃掉mid的右半边，但本身不能排除mid指针，right变更为mid指针
// 当mid等于右指针时，情况会比较复杂，经过测试用例我们无法判断旋转点是在哪个区间中
// 但我们可以判断的是，right指针无论在哪种情况下都不是最小的元素
// 所以我们让right指针-1，来剔除这个数字达到缩小范围的目的。
